/*
 * @lc app=leetcode.cn id=330 lang=javascript
 *
 * [330] 按要求补齐数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number}
 */
var minPatches = function (nums, n) {
  let result = 0;
  let x = 1;
  const size = nums.length;
  let i = 0;
  // 对于正整数 x，如果区间 [1,x−1]内的所有数字都已经被覆盖，且 x 在数组中，则区间 [1,2x−1]内的所有数字也都被覆盖。
  while (x <= n) {
    if (i < size && nums[i] <= x) {
      x += nums[i];
      i++;
    } else {
      x *= 2;
      result++;
    }
  }
  return result;
};
// @lc code=end
